package com.cqs.leetcode.recursion;

import java.util.LinkedList;
import java.util.Queue;

public class MatrixCellsinDistanceOrder1030 {


    static class Solution1{
        /***
         * 广度优先遍历的题目
         *
         * @param R
         * @param C
         * @param r0
         * @param c0
         * @return
         */
        public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
            boolean[][] handles = new boolean[R][C];
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{r0, c0});
            handles[r0][c0] = true;
            //一个有多少个点呢
            int[][] rs = new int[R * C][2];
            int cnt = -1;
            while (queue.size() > 0) {
                int size = queue.size();
                while (--size >= 0) {
                    int[] poll = queue.poll();
                    rs[++cnt] = poll;
                    //上下左右进行处理
                    int r = poll[0];
                    int c = poll[1];
                    //上
                    if (r > 0 && !handles[r - 1][c]) {
                        queue.add(new int[]{r - 1, c});
                        handles[r - 1][c] = true;
                    }
                    //下
                    if (r < R - 1 && !handles[r + 1][c]) {
                        queue.add(new int[]{r + 1, c});
                        handles[r + 1][c] = true;
                    }
                    //左边
                    if (c > 0 && !handles[r][c - 1]) {
                        queue.add(new int[]{r, c - 1});
                        handles[r][c - 1] = true;
                    }
                    //右边
                    if (c < C - 1 && !handles[r][c + 1]) {
                        queue.add(new int[]{r, c + 1});
                        handles[r][c + 1] = true;
                    }
                }
            }
            return rs;
        }
    }

}
